package com.ma.dp.subsequence;

import java.util.Arrays;

/**
 * @ClassName Solution1143
 * @Author: mayongqiang
 * @DATE 2022/4/5 19:11
 * @Description: 最长递增子序列 longest common subsequence. lcs问题
 */
public class Solution1143 {
    /*
        子序列问题，穷举出所有可能的结果并不显示     动态规划-->穷举+剪枝
        套路：dp table 二维数组  两个维度表示给定两数组的索引
            1、明确dp数组的含义
                dp[i][j]代表 子问题s1[1..i]与s2[1..j] 他们的LCS长度为dp[i][j]
                s1 = "ace"  s2 = "babcde" 则 dp[2][4]=2代表 对于 "ac" "babc" 他们的LCS=2     最终的答案为dp[3][6]
            2、定义base case索引为0的行与列表示空串 子序列自然为空
                dp[0][...] 与 dp[...][0]都应该初始化为0
            3、拟状态转移方程 “当前问题与子问题的关系”
                if(str[i]==str[j])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
     */
    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence03("ace", "babcde"));
    }

    /*1、递归暴力解法 */
    public static int longestCommonSubsequence01(String text1, String text2) {
        //return dp(text1, text2, text1.length() - 1, text2.length() - 1);
        return dp1(text1, text2, 0, 0);
    }

    // 暴力解法的递归法  1.1、自底向上的解法  dp(i,j)表示子字符str1(0..i)与str2(0..j)的LCS
    static int dp(String text1, String text2, int i, int j) {
        // base case
        if (i == -1 || j == -1) {
            return 0;
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            //找到一个在lcs中的元素，继续往前找
            return dp(text1, text2, i - 1, j - 1) + 1;
        } else {
            // 谁能让lcs长就听谁的
            return Math.max(dp(text1, text2, i - 1, j), dp(text1, text2, i, j - 1));
        }

    }

    // 递归解法  1.2、自顶向上的解法   dp[i][j] 表示str(i..)str(j..)的LCS
    static int dp1(String text1, String text2, int i, int j) {
        // base case
        if (i == text1.length() || j == text2.length()) {
            return 0;
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            //找到一个在lcs中的元素，继续往前找
            return dp1(text1, text2, i + 1, j + 1) + 1;
        } else {
            // 谁能让lcs长就听谁的
            return Math.max(dp1(text1, text2, i + 1, j), dp1(text1, text2, i, j + 1));
        }
    }

    /*2、带备忘录解法 仍旧是递归解法，利用备忘录做剪枝 */
    static int[][] memo;

    public static int longestCommonSubsequence02(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        //return dp3(text1, text2, m - 1, n - 1);
        return dp4(text1, text2, 0, 0);
    }

    //2.1 自底向上 dp(i,j)表示子字符str1(0..i)与str2(0..j)的LCS
    static int dp3(String text1, String text2, int i, int j) {
        if (i == -1 || j == -1) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            memo[i][j] = 1 + dp3(text1, text2, i - 1, j - 1);
        } else {
            memo[i][j] = Math.max(dp3(text1, text2, i - 1, j), dp3(text1, text2, i, j - 1));
        }
        return memo[i][j];
    }

    //2.2 自顶向下 dp[i][j]代表字符串str1(i..)str2(j..)的LCS
    static int dp4(String text1, String text2, int i, int j) {
        if (i == text1.length() || j == text2.length()) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            memo[i][j] = 1 + dp4(text1, text2, i + 1, j + 1);
        } else {
            memo[i][j] = Math.max(dp4(text1, text2, i + 1, j), dp4(text1, text2, i, j + 1));
        }
        return memo[i][j];
    }

    /*3、动态规划解法  采用动态规划就是要用自底向上的办法！*/
    public static int longestCommonSubsequence03(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // base case 即 dp[0][..] dp[..][0] 都初始化为0
        // dp[i][j] 代表 s1[0..i-1]s2[0..j-1]的LCS
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];

    }


}
